package hashtable.happynumber;

/**题目:
   编写一个算法来判断一个数 n 是不是快乐数。
   「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为  1，那么这个数就是快乐数。
   如果 n 是快乐数就返回 True ；不是，则返回 False 。

 * 示例：
   输入：19
   输出：true

 * 解释：
   1^2 + 9^2 = 82
   8^2 + 2^2 = 68
   6^2 + 8^2 = 100
   1^2 + 0^2 + 0^2 = 1
 */

import java.util.HashSet;
import java.util.Set;

/**方法一:哈希表
 * 这道题目看上去貌似一道数学问题，其实并不是！
  题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！
 * 正如：关于哈希表，你该了解这些！ (opens new window)中所说，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。
 * 所以这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。
 */
//步骤
    //初始化集合set,吧n加入set
    //把n替换为它每个位置上的数字的平方和，并加入set
    //重复这个过程，一直到新出现的数字等于1时返回 true，或新出现的数字已经存在在set中返回 false
public class HappyNumber {
    public boolean isHappy(int n) {
        Set<Integer> set = new HashSet<>();
        set.add(n);
        while (n != 1) {
            n = bitSquareSum(n);
            if (set.contains(n)) {
                return false;
            }
            set.add(n);
        }
        return true;
    }

    //辅助函数bitSquareSum用来计算n每个位置上的数字的平方和
    public int bitSquareSum(int n) {
        int sum = 0;
        while (n > 0) {
            int bit = n % 10;
            sum += bit * bit;
            n /= 10;
        }
        return sum;
    }
}

/**方法二:快慢指针
 * 把转换过程中每一个数据看作单链表的一个节点，将1看作单链表的最后一个元素，如果无法从n转换为1，则说明该链表会无限循环，否则会最终变为1。
 */
//当你看到循环二字之时，请无理由使用快慢指针
//步骤
    //初始化两个指针，一个指针fast，一个指针slow，将fast和slow都初始化为n
    //在slow不等于fast的情况下，每次slow转换一次，fast转换俩次
    //当slow等于fast时，如果slow=1,则为快乐数，否则为非快乐数
class Solution {
    public boolean isHappy(int n) {
        int slow=n,fast=n;
        do{
            slow=bitSquareSum(slow);
            fast=bitSquareSum(fast);
            fast=bitSquareSum(fast);
        }while(slow!=fast);
        return (slow==1);
    }

    public int bitSquareSum(int n){
        int sum=0;
        while(n>0){
            int bit=n%10;
            sum+=bit*bit;
            n/=10;
        }
        return sum;
    }
}
